updated: 2022-01-23_12:32:30-05:00
Theorem: The class of regular languages is closed under complementation
Proof:
Let A be a regular language
Let M be the DFA that accepts A
Let M' be the result of switching the accepting states of every state in M
if then
then
we claim
how do we prove this?
Suppose then lead to an accepting state in
leads to the same state in but that is not an accepting state in
if then accepts it
if then accepts it